import java.util.Arrays;

/**
 * @author ChenJunhong
 * @date 2018/10/31
 * Description:
 * 基本的思想就是分组以后继续使用插入排序的方式进行排序
 */
public class ShellSort {
    public static void shellSort(int[] arr){
        int delta;
        // 定义分组的间隔，初始为数组长度的2的一半
        for(delta = arr.length/2; delta >= 1 ; delta/=2){
            // 以下就是插入排序的过程
            for (int i = delta; i < arr.length ; i++) {
                int j = i;
                int tmp = arr[i];
                // 这里与插入式排序不一样，是可以 = 0的，此时代表的是数组的第0个元素
                while (j - delta >= 0 && tmp < arr[j - delta]){
                    arr[j] = arr[j - delta];
                    j -= delta;
                }
                arr[j] = tmp;
                System.out.println(Arrays.toString(arr));
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {34,5,6,3,1,8};
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
    }
}
